package practice;

/**
 * @program: leetcode
 * @description:
 * @author: za2599@gmail.com
 * @create: 2022-06-30 22:33
 **/
public class L0279 {


    private int[] array = new int [] {1,1,2,3,1,2,3,4,2,1,2,3,3,2,3,4,1,2,2,3,2,3,3,4,3,1,2,3,4,2,3,4,2,3,2,3,1,2,3,4,2,2,3,3,3,2,3,4,3,1,2,3,2,2,3,4,3,3,2,3,4,2,3,4,1,2,3,3,2,3,3,4,2,2,2,3,3,3,3,4,2,1,2,3,3,2,3,4,3,2,2,3,4,3,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,4,2,3,3,2,2,3,4,3,1,2,3,4,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,1,2,2,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,2,3,2,3,3,4,3,1,2,3,3,2,3,4,3,3,2,3,2,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,2,3,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,1,2,3,3,2,3,4,2,2,2,3,3,3,3,4,4,2,2,3,2,2,3,4,3,3,2,3,4,3,3,4,1,2,3,3,2,2,3,4,3,2,3,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,2,1,2,3,2,2,3,4,2,3,2,3,3,3,3,4,3,2,2,3,3,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,1,2,3,4,2,3,3,3,3,2,3,4,3,2,2,3,2,3,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,3,3,4,2,1,2,3,3,2,3,4,4,2,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,2,3,4,2,3,2,3,3,2,3,4,1,2,3,3,2,2,3,4,3,2,2,3,4,3,3,4,2,3,3,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,3,3,2,3,3,4,3,1,2,3,4,2,3,4,4,2,2,3,2,3,3,4,3,2,2,3,3,2,3,4,2,3,2,3,2,3,3,4,3,3,3,3,4,2,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,4,3,3,3,2,3,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,1,2,3,3,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,2,3,4,3,3,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,1,2,2,3,2,3,3,4,2,2,2,3,3,3,3,4,2,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,3,3,2,3,2,2,3,4,3,2,3,3,3,3,3,4,4,1,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,3,3,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,1,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,2,3,4,2,3,4,3,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,2,3,2,3,2,2,3,4,3,1,2,3,4,2,3,4,3,3,2,3,2,3,3,4,3,2,2,3,3,3,3,4,4,3,2,3,3,2,3,4,3,2,3,3,4,2,3,4,3,2,3,3,2,2,3,4,2,3,2,3,3,3,3,4,1,2,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,2,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,2,2,3,3,3,3,3,4,3,1,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,3,3,3,4,2,2,3,3,3,2,3,4,4,2,2,3,2,3,3,4,3,3,2,3,4,3,3,4,3,3,2,3,1,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,2,2,3,3,3,2,3,4,3,3,3,3,3,2,3,4,3,2,2,3,4,3,3,4,4,1,2,3,2,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,2,2,3,4,3,2,2,3,4,3,3,4,3,3,3,3,3,2,3,4,2,3,3,3,3,3,3,4,4,2,2,3,3,2,3,4,3,2,2,3,4,2,3,4,1,2,3,3,2,3,3,4,3,2,3,3,3,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,4,2,3,4,3,3,2,3,2,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,2,1,2,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,3,3,3,2,2,3,4,3,2,2,3,3,3,3,4,4,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,2,2,2,3,1,2,3,4,2,3,3,3,3,2,3,4,2,3,2,3,2,3,3,4,3,3,3,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,3,3,4,2,1,2,3,3,2,3,4,3,2,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,3,2,3,3,2,3,4,4,3,3,3,2,3,3,4,3,3,2,3,4,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,3,3,3,4,1,2,3,3,2,2,3,4,3,2,2,3,4,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,3,3,2,3,3,4,3,3,3,3,4,2,3,4,3,2,2,3,2,3,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,3,1,2,3,4,2,3,4,3,2,2,3,3,2,3,4,2,2,3,3,3,3,3,4,4,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,2,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,4,3,3,4,2,3,3,3,1,2,3,4,2,3,2,3,3,2,3,4,3,3,2,3,2,3,3,4,3,2,2,3,4,2,3,4,4,3,3,3,2,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,2,2,3,4,3,3,3,3,4,3,3,4,3,3,3,3,2,3,3,4,3,2,2,3,3,2,3,4,4,1,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,3,3,3,4,2,3,2,3,3,2,3,4,2,2,3,3,2,2,3,4,3,3,3,3,4,2,3,4,2,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,3,2,3,4,2,3,4,1,2,2,3,2,3,3,4,3,2,3,3,3,2,3,4,2,3,2,3,2,2,3,4,3,2,3,3,4,2,3,4,3,3,3,3,2,2,3,4,2,3,2,3,3,3,3,4,4,2,3,3,3,3,3,4,3,2,2,3,4,3,3,4,2,2,2,3,3,2,3,4,3,3,3,3,3,3,3,4,3,1,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,3,3,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,2,3,4,3,2,3,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,2,3,1,2,3,4,2,2,3,3,3,2,3,4,4,2,3,3,2,2,3,4,3,3,3,3,4,2,3,4,4,3,3,3,2,3,3,4,2,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,3,3,2,3,3,4,2,3,3,3,3,3,3,4,3,3,3,3,2,2,3,4,3,1,2,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,2,2,2,3,3,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,3,3,3,4,3,3,2,3,3,2,3,4,4,3,2,3,2,3,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,3,2,3,3,2,3,4,1,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,3,3,4,4,2,3,3,3,2,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,3,1,2,3,3,2,3,4,4,3,2,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,3,2,3,4,3,3,2,3,4,3,3,4,2,2,3,3,2,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,3,3,1,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,2,3,4,2,3,4,3,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,4,2,3,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,2,3,2,3,3,4,3,3,2,3,3,3,3,4,2,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,1,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,3,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,2,3,3,4,3,3,3,3,4,2,3,4,3,2,3,3,2,3,3,4,3,2,3,3,3,2,3,4,4,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,1,2,2,3,2,2,3,4,2,2,2,3,3,3,3,4,2,3,3,3,3,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,2,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,3,2,3,4,3,3,2,3,4,3,3,4,2,3,3,3,2,3,3,4,3,2,2,3,3,2,3,4,2,2,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,1,2,3,2,2,3,4,3,3,2,3,3,3,3,4,4,2,3,3,2,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,2,3,2,3,2,3,3,4,3,3,2,3,4,3,3,4,3,2,2,3,2,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,3,3,3,4,3,3,3,3,4,2,3,4,4,3,2,3,1,2,3,4,2,3,3,3,3,2,3,4,2,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,3,2,3,3,3,2,3,4,2,3,3,3,3,3,3,4,4,2,3,3,2,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,3,3,2,3,3,3,3,4,3,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,2,2,2,3,3,2,3,4,2,1,2,3,3,2,3,4,3,2,2,3,2,3,3,4,3,2,3,3,4,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,2,3,4,3,3,4,3,2,3,3,3,3,3,4,2,2,3,3,3,2,3,4,4,3,3,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,2,3,4,1,2,3,3,2,3,3,4,3,2,3,3,4,3,3,4,2,3,2,3,3,2,3,4,3,2,3,3,3,3,3,4,3,3,2,3,2,2,3,4,3,2,2,3,4,2,3,4,3,2,2,3,2,3,3,4,3,3,2,3,3,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,3,3,2,2,3,4,2,3,3,3,3,2,3,4,4,2,3,3,2,3,3,4,3,1,2,3,4,2,3,4,3,2,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,3,3,3,3,2,3,4,3,2,2,3,3,2,3,4,3,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,2,3,3,3,3,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,3,3,1,2,3,4,2,3,3,3,3,2,3,4,4,2,2,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,3,3,3,3,3,4,2,2,3,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,3,2,3,3,2,3,4,3,2,3,3,3,2,3,4,3,2,3,3,4,2,3,4,4,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,1,2,3,2,2,3,4,3,2,2,3,4,2,3,4,3,2,2,3,2,3,3,4,3,2,2,3,3,3,3,4,4,3,3,3,2,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,2,3,4,3,3,3,3,3,2,3,4,2,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,2,3,2,3,3,2,3,4,2,3,2,3,3,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,4,2,3,4,1,2,3,3,2,2,3,4,3,2,2,3,3,3,3,4,2,3,3,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,2,3,3,3,2,3,4,4,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,2,3,2,3,2,2,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,2,3,2,3,3,3,3,4,3,1,2,3,3,2,3,4,3,2,2,3,4,3,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,2,3,4,2,2,3,3,2,2,3,4,3,3,3,3,4,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,3,3,3,4,4,2,2,3,2,3,3,4,3,2,3,3,4,3,3,4,2,2,2,3,2,3,3,4,3,3,2,3,3,2,3,4,3,3,3,3,3,2,3,4,3,3,3,3,4,2,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,3,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,2,2,3,3,3,3,4,2,3,3,3,3,3,3,4,3,3,3,3,2,2,3,4,3,3,2,3,4,3,3,4,3,2,3,3,2,3,3,4,3,2,2,3,3,3,3,4,4,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,3,3,2,2,3,4,2,3,2,3,3,2,3,4,3,3,2,3,3,3,3,4,3,1,2,3,4,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,3,2,3,4,3,2,2,3,2,2,3,4,3,3,3,3,4,2,3,4,4,3,3,3,2,3,3,4,2,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,3,2,3,3,3,3,4,4,3,3,3,3,2,3,4,3,2,2,3,4,2,3,4,3,3,3,3,3,2,3,4,2,2,3,3,3,3,3,4,1,2,2,3,2,3,3,4,3,2,2,3,4,2,3,4,2,2,3,3,2,3,3,4,3,2,2,3,3,3,3,4,3,3,3,3,2,2,3,4,3,3,3,3,4,2,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,3,3,4,2,2,3,3,3,3,3,4,3,2,3,3,4,2,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,3,3,4,4,2,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,3,3,3,2,3,3,4,3,1,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,2,3,2,3,2,3,3,4,3,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,3,3,4,3,2,3,3,3,2,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,3,3,4,2,3,3,3,3,2,3,4,4,2,2,3,3,3,3,4,3,2,3,3,4,3,3,4,4,3,2,3,1,2,3,4,2,3,3,3,3,2,3,4,2,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,2,2,3,4,3,3,4,2,3,3,3,2,3,3,4,3,3,3,3,3,2,3,4,2,3,2,3,2,2,3,4,3,2,3,3,4,3,3,4,3,3,3,3,2,3,3,4,2,3,2,3,3,3,3,4,4,3,3,3,3,3,3,4,3,2,3,3,4,2,3,4,3,1,2,3,3,2,3,4,3,2,2,3,3,3,3,4,3,2,2,3,2,2,3,4,3,3,2,3,4,3,3,4,2,2,3,3,3,2,3,4,3,3,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,4,2,2,3,2,3,3,4,2,2,3,3,3,2,3,4,3,2,2,3,2,3,3,4,3,2,2,3,4,3,3,4,3,3,3,3,2,2,3,4,2,2,3,3,3,3,3,4,4,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,1,2,3,3,2,3,3,4,3,2,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,2,2,2,3,3,2,3,4,3,3,3,3,4,3,3,4,3,3,2,3,2,3,3,4,3,2,3,3,3,2,3,4,4,3,2,3,2,3,3,4,3,2,3,3,4,3,3,4,3,1,2,3,3,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,2,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,3,3,4,3,3,3,3,4,3,3,4,3,2,2,3,3,2,3,4,2,2,2,3,3,3,3,4,4,2,2,3,3,3,3,4,3,3,2,3,4,2,3,4,2,3,3,3,1,2,3,4,2,2,3,3,3,2,3,4,3,2,3,3,2,2,3,4,3,3,3,3,4,2,3,4,2,2,3,3,2,3,3,4,2,3,2,3,3,2,3,4,3,3,3,3,3,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,2,2,3,4,3,3,2,3,3,3,3,4,2,3,3,3,2,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,4,3,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,3,3,3,4,3,1,2,3,3,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,2,3,4,3,3,3,3,3,3,3,4,3,2,2,3,4,3,3,4,4,2,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,3,3,4,3,3,2,3,4,2,3,4,3,3,3,3,2,2,3,4,3,3,2,3,3,2,3,4,4,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,2,3,2,3,2,3,3,4,2,3,2,3,3,2,3,4,1,2,2,3,2,3,3,4,3,2,3,3,4,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,3,2,3,4,3,3,4,2,2,3,3,3,3,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,3,2,3,4,4,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,2,3,3,3,3,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,1,2,3,4,2,3,4,2,3,2,3,2,3,3,4,3,2,2,3,3,3,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,2,3,4,3,2,2,3,2,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,3,3,4,3,3,4,3,3,2,3,3,3,3,4,2,3,2,3,3,3,3,4,4,2,2,3,2,3,3,4,3,3,3,3,4,2,3,4,3,3,3,3,2,2,3,4,3,3,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,2,3,3,3,1,2,3,4,2,2,3,3,3,2,3,4,3,2,3,3,2,3,3,4,3,3,3,3,4,2,3,4,3,3,2,3,2,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,3,3,4,3,2,3,3,3,2,3,4,4,3,3,3,3,2,3,4,3,2,2,3,4,3,3,4,3,2,3,3,2,3,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,2,3,4,3,2,2,3,4,2,3,4,2,3,3,3,3,3,3,4,2,3,3,3,3,3,3,4,3,1,2,3,2,2,3,4,3,3,2,3,4,3,3,4,4,2,2,3,3,3,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,2,3,4,3,2,3,3,4,2,3,4,3,3,2,3,3,3,3,4,2,3,2,3,3,2,3,4,4,2,3,3,2,3,3,4,3,2,2,3,4,3,3,4,2,2,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,3,3,3,2,2,3,4,3,3,3,3,4,3,3,4,3,2,3,3,2,3,3,4,3,2,2,3,3,2,3,4,3,3,3,3,3,3,3,4,3,3,3,3,4,3,3,4,1,2,2,3,2,2,3,4,3,2,2,3,3,2,3,4,2,3,2,3,2,3,3,4,3,2,2,3,4,2,3,4,3,3,2,3,2,3,3,4,2,3,3,3,3,3,3,4,4,2,2,3,3,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,2,3,3,3,3,2,3,4,3,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,3,3,2,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,3,3,3,4,2,1,2,3,3,2,3,4,3,2,2,3,4,2,3,4,3,2,3,3,3,3,3,4,3,2,2,3,3,3,3,4,4,3,3,3,2,2,3,4,3,3,3,3,4,3,3,4,3,3,2,3,2,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,4,3,3,4,2,2,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,3,2,3,4,3,3,3,3,4,2,3,4,2,2,3,3,2,2,3,4,3,2,2,3,3,3,3,4,3,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,3,3,1,2,3,4,2,3,2,3,3,2,3,4,4,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,2,3,3,4,2,2,3,3,3,2,3,4,3,2,3,3,2,2,3,4,3,3,3,3,4,3,3,4,2,2,3,3,2,3,3,4,3,2,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,3,3,4,3,3,4,4,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,3,3,4,2,3,3,3,3,3,3,4,4,2,2,3,2,3,3,4,3,1,2,3,4,2,3,4,3,3,2,3,2,3,3,4,3,2,3,3,3,2,3,4,2,3,2,3,2,2,3,4,3,2,3,3,4,2,3,4,3,3,2,3,2,2,3,4,2,3,2,3,3,3,3,4,3,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,3,2,3,4,3,3,2,3,3,3,3,4,3,2,2,3,2,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,2,2,3,4,3,2,3,3,3,2,3,4,4,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,2,3,3,3,3,2,3,4,3,2,2,3,3,3,3,4,1,2,3,3,2,3,3,4,3,2,3,3,4,3,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,2,3,4,4,3,3,3,2,2,3,4,3,2,2,3,4,3,3,4,4,3,3,3,3,3,3,4,3,2,3,3,3,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,2,3,3,4,3,1,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,2,3,4,3,2,2,3,2,3,3,4,2,3,3,3,3,2,3,4,2,3,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,2,3,4,3,2,2,3,3,3,3,4,4,2,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,3,3,3,3,3,3,4,3,2,3,3,3,2,3,4,2,3,3,3,3,2,3,4,3,3,3,3,4,3,3,4,3,3,2,3,2,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,2,3,3,4,3,2,2,3,4,3,3,4,4,3,2,3,1,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,2,3,3,3,3,3,4,2,2,2,3,3,2,3,4,4,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,3,3,2,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,4,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,3,3,3,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,3,3,2,3,3,4,3,2,2,3,3,2,3,4,2,3,3,3,2,2,3,4,3,3,3,3,4,3,3,4,3,1,2,3,3,2,3,4,3,3,2,3,3,2,3,4,4,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,2,2,2,3,3,2,3,4,2,3,2,3,3,3,3,4,3,3,2,3,2,3,3,4,3,3,3,3,4,2,3,4,2,2,3,3,3,2,3,4,3,3,3,3,3,2,3,4,3,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,3,3,3,3,2,3,4,4,2,3,3,2,2,3,4,3,3,3,3,4,2,3,4,1,2,3,3,2,3,3,4,2,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,2,2,3,3,2,2,3,4,3,3,3,3,4,3,3,4,3,2,2,3,2,3,3,4,3,2,2,3,3,3,3,4,4,3,2,3,2,3,3,4,3,2,3,3,4,2,3,4,3,2,2,3,3,3,3,4,3,3,3,3,3,3,3,4,2,3,3,3,2,3,3,4,3,2,2,3,4,3,3,4,2,1,2,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,4,3,3,4,4,3,3,3,2,2,3,4,3,3,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,3,3,3,3,2,3,4,4,2,2,3,3,3,3,4,3,2,3,3,4,2,3,4,2,3,2,3,2,2,3,4,2,3,3,3,3,3,3,4,3,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,3,2,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,2,3,3,3,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,1,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,3,3,3,2,3,4,2,2,3,3,3,3,3,4,4,3,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,3,3,3,4,2,3,3,3,3,2,3,4,3,3,3,3,4,2,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,3,2,2,3,3,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,3,3,3,2,2,3,4,3,1,2,3,3,2,3,4,4,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,3,2,3,3,2,3,4,2,2,2,3,3,2,3,4,2,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,3,3,3,3,2,2,3,4,3,2,3,3,3,2,3,4,3,2,2,3,2,3,3,4,3,3,2,3,4,3,3,4,2,2,3,3,2,3,3,4,2,3,3,3,3,2,3,4,3,3,2,3,3,2,3,4,3,2,2,3,4,3,3,4,3,3,2,3,2,2,3,4,2,3,2,3,3,3,3,4,4,2,3,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,3,3,3,2,3,4,2,3,3,3,3,3,3,4,1,2,2,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,2,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,3,3,4,4,2,3,3,2,2,3,4,3,3,2,3,3,3,3,4,2,2,3,3,2,3,3,4,3,2,3,3,4,3,3,4,3,2,3,3,3,2,3,4,3,2,2,3,3,3,3,4,4,3,2,3,2,2,3,4,3,3,2,3,4,2,3,4,4,3,3,3,3,2,3,4,3,2,2,3,3,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,2,3,2,3,2,3,3,4,2,2,3,3,3,2,3,4,3,3,2,3,2,3,3,4,3,1,2,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,2,3,3,3,3,3,4,2,3,2,3,3,3,3,4,4,2,3,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,2,3,2,2,3,4,3,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,2,3,4,3,3,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,3,3,3,4,3,2,3,3,3,2,3,4,2,3,3,3,2,2,3,4,3,3,3,3,4,2,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,4,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,3,3,3,4,2,2,3,3,3,3,3,4,3,3,2,3,2,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,2,3,4,3,2,2,3,3,3,3,4,3,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,2,2,3,3,2,3,3,4,2,2,3,3,3,2,3,4,3,3,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,4,2,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,3,3,3,2,3,3,4,3,2,3,3,3,2,3,4,3,1,2,3,3,2,3,4,3,2,2,3,4,3,3,4,3,2,2,3,3,2,3,4,2,3,2,3,3,3,3,4,3,3,3,3,2,2,3,4,3,3,2,3,4,3,3,4,4,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,2,2,3,3,3,3,3,4,3,3,2,3,4,3,3,4,3,2,2,3,2,3,3,4,3,3,3,3,3,3,3,4,4,3,2,3,3,2,3,4,3,2,3,3,4,2,3,4,3,2,3,3,2,2,3,4,2,3,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,3,2,3,4,2,3,4,2,2,3,3,3,2,3,4,2,3,3,3,3,3,3,4,3,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,1,2,3,3,2,3,3,4,3,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,3,3,4,3,2,2,3,3,2,3,4,4,2,2,3,2,3,3,4,3,2,3,3,4,3,3,4,2,3,3,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,2,3,2,3,3,2,3,4,3,2,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,3,3,3,2,3,4,2,3,3,3,3,3,3,4,2,3,3,3,2,2,3,4,3,2,3,3,4,2,3,4,3,3,3,3,3,3,3,4,3,2,3,3,3,3,3,4,4,1,2,3,3,2,3,4,3,2,2,3,4,2,3,4,4,2,2,3,2,3,3,4,3,3,2,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,3,3,4,3,2,2,3,2,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,2,3,3,4,3,2,3,3,4,3,3,4,2,3,2,3,3,2,3,4,3,2,2,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,3,3,4,3,2,3,3,2,3,3,4,3,3,2,3,3,2,3,4,4,3,3,3,3,2,3,4,3,3,3,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,2,3,4,3,3,2,3,1,2,3,4,2,2,3,3,3,2,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,4,3,3,3,3,3,3,4,2,3,2,3,3,3,3,4,2,2,2,3,3,2,3,4,3,3,3,3,4,3,3,4,3,2,3,3,2,3,3,4,2,3,3,3,3,3,3,4,4,2,3,3,2,2,3,4,3,2,2,3,4,3,3,4,2,3,2,3,3,3,3,4,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,3,3,3,4,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,2,2,3,4,3,2,3,3,4,3,3,4,3,3,2,3,3,3,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,1,2,3,4,2,3,4,3,3,2,3,3,2,3,4,2,2,2,3,3,3,3,4,4,3,2,3,3,3,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,2,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,3,3,4,3,2,3,3,4,3,3,4,2,2,2,3,2,2,3,4,3,2,2,3,3,3,3,4,3,2,3,3,3,3,3,4,3,2,3,3,4,2,3,4,3,3,3,3,2,2,3,4,2,3,3,3,3,3,3,4,3,3,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,3,3,3,2,3,3,4,2,2,3,3,3,2,3,4,4,2,2,3,3,3,3,4,3,3,3,3,4,3,3,4,3,3,2,3,2,3,3,4,3,3,2,3,3,2,3,4,1,2,3,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,3,3,4,3,2,3,3,2,3,3,4,3,2,2,3,3,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,4,2,3,4,3,2,2,3,2,3,3,4,2,3,3,3,3,3,3,4,4,3,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,2,2,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,3,3,4,2,3,4,2,2,3,3,2,3,3,4,3,3,3,3,3,2,3,4,3,3,3,3,3,2,3,4,3,2,3,3,4,3,3,4,4,2,2,3,2,3,3,4,3,1,2,3,3,2,3,4,2,3,2,3,2,3,3,4,3,2,3,3,4,2,3,4,3,3,2,3,2,2,3,4,3,2,3,3,3,2,3,4,4,2,3,3,2,2,3,4,3,3,2,3,4,3,3,4,2,2,3,3,3,3,3,4,2,2,2,3,3,3,3,4,2,3,2,3,3,2,3,4,3,3,2,3,4,3,3,4,3,2,2,3,3,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,3,3,3,4,3,2,2,3,4,2,3,4,2,3,2,3,3,3,3,4,2,3,3,3,3,3,3,4,2,3,3,3,2,3,3,4,3,2,2,3,4,3,3,4,3,2,3,3,3,3,3,4,3,3,2,3,3,3,3,4,4,3,2,3,2,2,3,4,3,2,3,3,4,2,3,4,3,2,3,3,1,2,3,4,2,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,3,3,4,2,3,4,2,2,3,3,3,2,3,4,2,3,2,3,3,3,3,4,3,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,3,3,3,3,2,3,3,4,3,2,2,3,3,3,3,4,2,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,3,2,3,3,3,2,3,4,2,3,2,3,3,2,3,4,4,2,3,3,2,3,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,3,3,4,3,2,3,3,3,2,3,4,3,3,2,3,2,3,3,4,3,3,2,3,4,2,3,4,2,2,3,3,2,3,3,4,2,2,3,3,3,2,3,4,3,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,3,1,2,3,2,2,3,4,2,3,2,3,3,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,3,3,3,2,3,4,3,2,3,3,3,3,3,4,4,3,2,3,2,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,3,3,4,3,3,2,3,3,3,3,4,2,3,2,3,3,2,3,4,3,2,3,3,4,2,3,4,3,3,2,3,2,2,3,4,3,3,3,3,3,2,3,4,3,2,3,3,2,3,3,4,3,3,2,3,4,3,3,4,4,2,3,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,3,3,3,2,2,3,4,3,2,2,3,3,2,3,4,4,3,3,3,3,3,3,4,3,2,3,3,4,3,3,4,1,2,3,3,2,2,3,4,2,2,3,3,3,3,3,4,2,3,3,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,2,3,2,3,3,4,2,2,3,3,3,3,3,4,3,2,2,3,3,3,3,4,3,3,2,3,4,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,3,2,3,4,3,2,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,3,2,3,2,3,3,4,2,3,3,3,3,2,3,4,4,3,3,3,2,2,3,4,3,2,3,3,4,2,3,4,2,3,2,3,3,2,3,4,3,3,3,3,3,3,3,4,2,3,3,3,2,2,3,4,3,3,2,3,4,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,3,2,3,4,3,3,3,3,2,2,3,4,3,3,3,3,4,3,3,4,3,1,2,3,2,2,3,4,3,3,2,3,3,2,3,4,3,2,3,3,2,3,3,4,3,2,2,3,4,2,3,4,3,2,2,3,3,2,3,4,2,3,3,3,3,3,3,4,4,2,2,3,3,2,3,4,3,3,2,3,4,2,3,4,2,2,3,3,3,2,3,4,3,3,3,3,3,3,3,4,2,3,2,3,3,3,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,3,3,4,3,2,2,3,2,3,3,4,3,2,2,3,4,2,3,4,2,3,3,3,2,3,3,4,2,3,3,3,3,2,3,4,3,2,2,3,2,3,3,4,3,3,3,3,4,2,3,4,3,3,3,3,2,3,3,4,3,2,2,3,3,3,3,4,4,3,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,2,2,3,1,2,3,4,2,3,2,3,3,2,3,4,2,3,3,3,2,2,3,4,3,3,2,3,4,2,3,4,3,3,2,3,3,3,3,4,2,3,3,3,3,3,3,4,3,2,2,3,3,2,3,4,3,2,3,3,4,2,3,4,4,2,3,3,2,3,3,4,3,2,3,3,3,2,3,4,2,3,3,3,2,2,3,4,3,2,3,3,4,3,3,4,3,2,2,3,2,2,3,4,2,3,3,3,3,3,3,4,4,3,3,3,3,3,3,4,3,2,2,3,4,2,3,4,3,3,3,3,3,2,3,4,2,3,2,3,3,3,3,4,3,2,3,3,2,2,3,4,3,3,2,3,4,3,3,4,2,3,3,3,2,3,3,4,3,2,2,3,3,2,3,4,3,3,2,3,3,2,3,4,3,3,3,3,4,3,3,4,2,3,3,3,3,2,3,4,2,1,2,3,3,2,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,2,3,3,3,2,3,4,4,2,3,3,3,3,3,4,3,3,2,3,4,3,3,4,3,2,3,3,2,3,3,4,2,2,2,3,3,3,3,4,2,2,2,3,3,3,3,4,3,2,2,3,4,3,3,4,3,3,3,3,2,2,3,4,2,3,2,3,3,2,3,4,3,3,3,3,2,3,3,4,3,3,2,3,4,3,3,4,3,3,2,3,3,2,3,4,2,2,3,3,3,3,3,4,3,3,2,3,3,2,3,4,3,2,2,3,4,2,3,4,3,2,3,3,3,3,3,4,3,3,2,3,3,2,3,4,4,3,2,3,2,2,3,4,3,3,3,3,4,2,3,4,4,2,2,3,3,3,3,4,2,3,3,3,3,2,3,4,1};

    public int numSquares(int n) {
        return array[n];
    }



    public static void main(String[] args) {
        System.out.println(new L0279().numSquares(12)); // 3
        System.out.println(new L0279().numSquares(13)); // 2
//        System.out.println(new L0279().numSquares(10000)); // 2




    }
}
